package _interview75;

/**
 * 714. 买卖股票的最佳时机含手续费
 */
public class No714 {
    private int[] prices;
    private int[][] cache;
    private int fee;

    public int maxProfit(int[] prices, int fee) {
        this.prices = prices;
        this.fee = fee;
        int n = prices.length;
        cache = new int[n][2];
        return dfs(n - 1, 0);
    }

    private int dfs(int i, int state) {
        if (i < 0) return state == 0 ? 0 : Integer.MIN_VALUE / 2;
        else if (cache[i][state] != 0) return cache[i][state];
        else if (state == 1) return cache[i][state] = Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i]);
        else return cache[i][state] = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i] - fee);
    }
}
